#include "test.h"


BaseNode::BaseNode(const string &name) 
{
    this->nodeName = name;
    this->posX = -1;
    this->posY = -1;
}

void BaseNode::addPreNode(BaseNode *preNode) 
{
    if(find(this->preNodePtrs.begin(), this->preNodePtrs.end(), preNode) != this->preNodePtrs.end()) 
    {
        return;
    }

    this->preNodePtrs.push_back(preNode);
}

void BaseNode::print()
{
    cout<<this->nodeName<<"["<<this->posX<<","<<this->posY<<"]"<<"(";
    bool first=true;
    for(vector<BaseNode*>::iterator iter = this->preNodePtrs.begin(); iter != this->preNodePtrs.end(); iter++)
    {
        if(!first){
            cout<<", ";
        }
        cout<< (*iter)->nodeName;
        first=false;
    }
    cout<<")";
}

vector<BaseNode*> BaseNode::loop2CheckValid(vector<BaseNode*> & nodePathFromEnd, set<BaseNode*> & emptyPreNodes, set<BaseNode*> & nodes)
{
    if(find(nodePathFromEnd.begin(), nodePathFromEnd.end(), this) != nodePathFromEnd.end()) 
    {   
        // nodePathFromEnd 表示从尾节点 到 当前节点的 路径
        // 当前节点，出现在 nodePathFromEnd 中，表示发现环
        nodePathFromEnd.push_back(this);
        return nodePathFromEnd;
    }

    // 当前节点，加入nodePathFromEnd，为递归前置节点做准备
    nodePathFromEnd.push_back(this);

    // nodes 用于收集所有的节点
    nodes.insert(this);

    if(0 == this->preNodePtrs.size())
    {
        // emptyPreNodes 用于收集所有 前置节点为空的节点
        emptyPreNodes.insert(this);
    }

    // 终止 节点的 绘制坐标设定为 (0,0)
    if(this->posX < 0) {
        this->posX = 0;
    }
    if(this->posY < 0) {
        this->posY = 0;
    }

    int n=0;
    for(vector<BaseNode*>::iterator iter = this->preNodePtrs.begin(); iter != this->preNodePtrs.end(); iter++)
    {
        BaseNode* preNode = (*iter);

        // 绘制处理链，前置节点绘制坐标X设定为不小于 当前节点X+1
        if(preNode->posX < this->posX+1) {
            preNode->posX = this->posX+1;
        }
        // 绘制处理链，第n个前置节点绘制坐标Y设定为不小于 当前节点X+n
        if(preNode->posY < this->posY+n) {
            preNode->posY = this->posY+n;
        }

        vector<BaseNode*> nodePathFromEnd4PreNode(nodePathFromEnd);
        vector<BaseNode*> loopPath = preNode->loop2CheckValid(nodePathFromEnd4PreNode, emptyPreNodes, nodes);
        if(loopPath.size() > 0){
            return loopPath;
        }

        ++n;
    }

    vector<BaseNode*> empty;

    return empty;
}






ProcessGraph::ProcessGraph() {

}

void ProcessGraph::addNode(BaseNode * node)
{
    if(find(this->nodePtrs.begin(), this->nodePtrs.end(), node) != this->nodePtrs.end()) 
    {
        return;
    }

    this->nodePtrs.push_back(node);
}

void ProcessGraph::addNode2Node(BaseNode * nodeFrom, BaseNode * nodeTo) 
{
    if(nodeFrom == NULL || nodeTo == NULL)
    {
        return;
    }
    this->addNode(nodeFrom);
    this->addNode(nodeTo);
    nodeTo->addPreNode(nodeFrom);
}

// 添加一串 节点到 处理图
// node1 --> node2 --> nodeA --> nodeB --> nodeC --> nodeD --> nodeE --> nodeF
void ProcessGraph::addNodeSequece(vector<BaseNode*> & nodeSequece)
{
    if(1 == nodeSequece.size()){
        this->addNode(nodeSequece[0]);
        return;
    }
    // todo: 如上图，加入nodeSequece中的节点到处理流程图
    // 并且设定前后依赖关系
    for(int i = 0; i < nodeSequece.size()-1; i++)
    {
        this->addNode2Node(nodeSequece[i], nodeSequece[i+1]);
    }
}

// 添加 1 to n 节点到 处理图
// node1 -->   node2
//         ↘   nodeA
//         ↘   nodeB
//         ↘   nodeC
//         ↘   nodeD
//         ↘   nodeE
void ProcessGraph::addOne2MultiNodes(BaseNode * node, vector<BaseNode*> & nodeSequece)
{
    // todo: 如上图，加入nodeSequece中的节点 和  node 到处理流程图
    // 并且设定前后依赖关系

    for(int i = 0; i < nodeSequece.size(); i++)
    {
        this->addNode2Node(node, nodeSequece[i]);
    }
}

// 添加 n to 1 节点到 处理图
// node2 --------> nodeF
// nodeA ________↗
// nodeB ________↗
// nodeC ________↗
// nodeD ________↗
// nodeE ________↗
void ProcessGraph::addMultiNodes2One(vector<BaseNode*> & nodeSequece, BaseNode * node)
{
    // todo: 如上图，加入nodeSequece中的节点 和  node 到处理流程图
    // 并且设定前后依赖关系
    for(int i = 0; i < nodeSequece.size(); i++)
    {
        this->addNode2Node(nodeSequece[i], node);
    }
}

// 不能有环
// 有唯一的起点 和 终点
bool ProcessGraph::isValid(BaseNode * startNode, BaseNode * endNode)
{
    // todo: 以入参 startNode 作为起点，endNode 作为终点，计算当前处理图是否合法

    vector<BaseNode*> nodePathFromEnd;
    set<BaseNode*> emptyPreNodes;
    set<BaseNode*> nodesInGraph;

    vector<BaseNode*> loopPath = endNode->loop2CheckValid(nodePathFromEnd, emptyPreNodes, nodesInGraph);
    if(loopPath.size() > 0) 
    {
        cout<<"发现了环"<<endl<<"\t";
        for(vector<BaseNode*>::iterator iter = loopPath.begin(); iter != loopPath.end(); iter++)
        {
            cout<<(*iter)->nodeName<<", ";
        }
        return false;
    }



    if(emptyPreNodes.size() != 1) 
    {
        // 起点不唯一
        cout<<"起点不唯一"<<endl;
        for(set<BaseNode*>::iterator iter = emptyPreNodes.begin(); iter != emptyPreNodes.end(); iter++)
        {
            cout<<(*iter)->nodeName<<", ";
        }
        return false;
    }
    set<BaseNode*>::iterator itr =  emptyPreNodes.begin();
    if(startNode != (*itr))
    {
        // 起点 和 入参不一致
        cout<<"遍历找到的起点"<<(*itr)->nodeName<<" 和 入参起点"<<startNode->nodeName<<" 不一致"<<endl;
        return false;
    }

    if(nodesInGraph.size() != this->nodePtrs.size()) {
        // 处理节点，和深度优先递归遍历到的节点数量不同
        cout<<"处理节点，和深度优先递归遍历到的节点数量不同"<<endl;
        return false;
    }

    for(vector<BaseNode*>::iterator iter = this->nodePtrs.begin(); iter != this->nodePtrs.end(); iter++)
    {
        BaseNode* node = (*iter);
        if(nodesInGraph.find(node) == nodesInGraph.end())
        {
            // 处理链节点，和深度优先递归遍历到的节点 不全等
            cout<<"处理链节点，和深度优先递归遍历到的节点 不全等"<<endl;
            return false;
        }
    }


    return true;
    //return false;
}



// 打印图
void ProcessGraph::printGraph(BaseNode * startNode, BaseNode * endNode)
{
    // todo: 以入参 startNode 作为起点，endNode 作为终点，打印处理流程图
    cout<<endl<<"printGraph"<<endl;
    int maxX=-1;
    int maxY=-1;
    for(vector<BaseNode*>::iterator iter = this->nodePtrs.begin(); iter != this->nodePtrs.end(); iter++)
    {
        cout<<"\t";
        (*iter)->print();
        cout<<endl;

        if((*iter)->posX > maxX){
            maxX = (*iter)->posX;
        }
        if((*iter)->posY > maxY){
            maxY = (*iter)->posY;
        }
    }
    maxX += 1;
    maxY += 1;

    int xScale = 12;
    int yScale = 4;
    int charMatrixLen = xScale*maxX*yScale*maxY;
    char* charMatrix = new char(charMatrixLen);
    char* wptr = charMatrix;
    for(int loop=0; loop<charMatrixLen; ++loop) 
    {
        *wptr = ' ';
        wptr += 1;
    }

    for(vector<BaseNode*>::iterator iter = this->nodePtrs.begin(); iter != this->nodePtrs.end(); iter++)
    {
        int drawX = (maxX - (*iter)->posX)*xScale;
        int drawY = (*iter)->posY * yScale;
        char* wptr = charMatrix;
        wptr += (drawY * xScale*maxX + drawX);
        strcpy(wptr, (*iter)->nodeName.c_str());
    }

    cout<<endl;
    cout<<endl;
    wptr = charMatrix;
    for(int y=0; y<yScale*maxY; ++y)
    {
        for(int x=0; x<xScale*maxX; ++x)
        {
            cout<<(*wptr);
            wptr += 1;
        }
        cout<<endl;
    }
    // ↑↓←→
    // ↖↗↘↙↔
}














void processGraphCase1() {

    BaseNode *node1  = new BaseNode("node1");
    BaseNode *node2  = new BaseNode("node2");
    BaseNode *nodeA  = new BaseNode("nodeA");
    BaseNode *nodeB  = new BaseNode("nodeB");
    BaseNode *nodeC  = new BaseNode("nodeC");
    BaseNode *nodeD  = new BaseNode("nodeD");
    BaseNode *nodeE  = new BaseNode("nodeE");
    BaseNode *nodeF  = new BaseNode("nodeF");

// 串行 node1 --> node2 --> nodeA --> nodeB --> nodeC --> nodeD --> nodeE --> nodeF（end）

    ProcessGraph pg1;
    vector<BaseNode*> pg1NodeSequece {node1, node2, nodeA, nodeB, nodeC, nodeD, nodeE, nodeF};
    pg1.addNodeSequece(pg1NodeSequece);
    if(pg1.isValid(node1, nodeF)) 
    {   // 如果处理流程图合法，打印之
        pg1.printGraph(node1, nodeF);
    } 
    else 
    {   // 如果处理流程图不合法 报异常
        cout<<endl<<"pg1 not valid process graph"<<endl;
    }

    if(pg1.isValid(node2, nodeF)) 
    {   // 如果处理流程图合法，打印之
        pg1.printGraph(node2, nodeF);
    } 
    else 
    {   // 如果处理流程图不合法 报异常
        cout<<endl<<"pg1 not valid process graph"<<endl;
    }
}







void processGraphCase2() {

    BaseNode *node1  = new BaseNode("node1");
    BaseNode *node2  = new BaseNode("node2");
    BaseNode *nodeA  = new BaseNode("nodeA");
    BaseNode *nodeB  = new BaseNode("nodeB");
    BaseNode *nodeC  = new BaseNode("nodeC");
    BaseNode *nodeD  = new BaseNode("nodeD");
    BaseNode *nodeE  = new BaseNode("nodeE");
    BaseNode *nodeF  = new BaseNode("nodeF");

// 并行  node1 -->   node2 --------> nodeF（end）
//              ↘   nodeA ________↗
//              ↘   nodeB ________↗
//              ↘   nodeC ________↗
//              ↘   nodeD ________↗
//              ↘   nodeE ________↗
    ProcessGraph pg2;
    vector<BaseNode*> pg2NodeSequece {node2, nodeA, nodeB, nodeC, nodeD, nodeE};
    pg2.addOne2MultiNodes(node1, pg2NodeSequece);
    pg2.addMultiNodes2One(pg2NodeSequece, nodeF);
    if(pg2.isValid(node1, nodeF)) 
    {   // 如果处理流程图合法，打印之
        pg2.printGraph(node1, nodeF);
    } 
    else 
    {   // 如果处理流程图不合法 报异常
        cout<<endl<<"pg2 not valid process graph"<<endl;
    }
}








void processGraphCase3() {

    BaseNode *node1  = new BaseNode("node1");
    BaseNode *node2  = new BaseNode("node2");
    BaseNode *nodeA  = new BaseNode("nodeA");
    BaseNode *nodeB  = new BaseNode("nodeB");
    BaseNode *nodeC  = new BaseNode("nodeC");
    BaseNode *nodeD  = new BaseNode("nodeD");
    BaseNode *nodeE  = new BaseNode("nodeE");
    BaseNode *nodeF  = new BaseNode("nodeF");

// 带环的有向图
//     node1 -->  node2 -->  nodeC -->   nodeE --> nodeF（end）
//           --↘  nodeA -->  nodeD _____↗  |
//           --↘  nodeB _____↗             |
//                  ↑                      |
//                  ↑______________________|
    ProcessGraph pg3;
    vector<BaseNode*> pg3NodeSequece1 {node1, node2, nodeC, nodeE, nodeF};
    pg3.addNodeSequece(pg3NodeSequece1);
    vector<BaseNode*> pg3NodeSequece2 {node1, nodeA, nodeD, nodeE};
    pg3.addNodeSequece(pg3NodeSequece2);
    vector<BaseNode*> pg3NodeSequece3 {node1, nodeB, nodeD};
    pg3.addNodeSequece(pg3NodeSequece3);
    vector<BaseNode*> pg3NodeSequece4 {nodeE, nodeB};
    pg3.addNodeSequece(pg3NodeSequece4);
    if(pg3.isValid(node1, nodeF)) 
    {   // 如果处理流程图合法，打印之
        pg3.printGraph(node1, nodeF);
    } 
    else 
    {   // 如果处理流程图不合法 报异常
        cout<<endl<<"pg3 not valid process graph"<<endl;
    }
}








void processGraphCase4() {

    BaseNode *node1  = new BaseNode("node1");
    BaseNode *node2  = new BaseNode("node2");
    BaseNode *nodeA  = new BaseNode("nodeA");
    BaseNode *nodeB  = new BaseNode("nodeB");
    BaseNode *nodeC  = new BaseNode("nodeC");
    BaseNode *nodeD  = new BaseNode("nodeD");
    BaseNode *nodeE  = new BaseNode("nodeE");
    BaseNode *nodeF  = new BaseNode("nodeF");

// 起始节点不唯一
//                                 nodeB ---↘
// node1 --> node2 -->  nodeC -->  nodeE --> nodeF（end）
//        ↘  nodeA -->  nodeD _____↗
    ProcessGraph pg4;
    vector<BaseNode*> pg4NodeSequece1 {node1, node2, nodeC, nodeE, nodeF};
    pg4.addNodeSequece(pg4NodeSequece1);
    vector<BaseNode*> pg4NodeSequece2 {node1, nodeA, nodeD, nodeE};
    pg4.addNodeSequece(pg4NodeSequece2);
    vector<BaseNode*> pg4NodeSequece3 {nodeB, nodeF};
    pg4.addNodeSequece(pg4NodeSequece3);

    if(pg4.isValid(node1, nodeF)) 
    {   // 如果处理流程图合法，打印之
        pg4.printGraph(node1, nodeF);
    } 
    else 
    {   // 如果处理流程图不合法 报异常
        cout<<endl<<"pg4 not valid process graph"<<endl;
    }
}

void processGraphCase5() {

    BaseNode *node1  = new BaseNode("node1");
    BaseNode *node2  = new BaseNode("node2");
    BaseNode *nodeA  = new BaseNode("nodeA");
    BaseNode *nodeB  = new BaseNode("nodeB");
    BaseNode *nodeC  = new BaseNode("nodeC");
    BaseNode *nodeD  = new BaseNode("nodeD");
    BaseNode *nodeE  = new BaseNode("nodeE");
    BaseNode *nodeF  = new BaseNode("nodeF");


    // 串并行 node1 --> node2 -->  nodeC -->  nodeE --> nodeF（end）
    //              ↘ nodeA -->  nodeD _______↗
    //              ↘ nodeB __________________↗
    ProcessGraph pg5;
    vector<BaseNode*> sequece1 {node1, node2, nodeC, nodeE, nodeF};
    pg5.addNodeSequece(sequece1);
    vector<BaseNode*> sequece2 {node1, nodeA, nodeD, nodeE};
    pg5.addNodeSequece(sequece2);
    vector<BaseNode*> sequece3 {node1, nodeB, nodeE};
    pg5.addNodeSequece(sequece3);

    if(pg5.isValid(node1, nodeF)) 
    {   // 如果处理流程图合法，打印之
        pg5.printGraph(node1, nodeF);
    } 
    else 
    {   // 如果处理流程图不合法 报异常
        cout<<endl<<"pg5 not valid process graph"<<endl;
    }
}

int processGraphDemo() {
//int main() {
    processGraphCase1();
    processGraphCase2();
    processGraphCase3();
    processGraphCase4();
    processGraphCase5();
    return 0;
}
